package com.msb._02位运算;

import jdk.internal.org.objectweb.asm.tree.analysis.BasicValue;
import jdk.internal.org.objectweb.asm.tree.analysis.Value;

import javax.swing.text.html.MinimalHTMLWriter;

/**
 * @author whf
 * 测试链接：https://leetcode.com/problems/divide-two-integers
 * @date 2024-12-17 15:21
 */
public class _13位运算实现加减乘除 {

    public static void main(String[] args) {
        int a = 10;
        int b = 3;
        System.out.println(divide(a,b));
    }
    
    // 加法等于无进位加(^)加上进位(& << 1)
    // 然后由于不能用加法, 用循环知道进位为0
    public static int add(int a, int b) {
        int sum = a;
        while (b != 0) {
            sum = a ^ b;
            b = (a & b) << 1;
            a = sum;
        }
        return sum;
    }

    public static int negNum(int n) {
        return add(~n, 1);
    }

    // 减法就是加一个负数
    // 负数就是~然后+1
    public static int minus(int a, int b) {
        return add(a, negNum(b));
    }

    // 假设乘数a和b, b的二进制位是1就保留, 其他的只做a的移位, 最后结果相加
    // b >>>不能带符号, 考虑负数
    public static int multi(int a, int b) {
        int res = 0;
        while (b != 0) {
            if ((b & 1) == 1) {
                res = add(a, res);
            }
            a <<= 1;
            b >>>= 1;
        }
        return res;
    }

    public static boolean isNeg(int n) {
        return n < 0;
    }

    // 只能计算正值
    // 假设a/b, a慢慢右移直到>b, 那么那个二进制就为1, 然后a减去b左移那个位置
    // 结果通过符号位^得到
    public static int div(int a, int b) {
        int aValue = isNeg(a) ? negNum(a) : a;
        int bValue = isNeg(b) ? negNum(b) : b;
        int res = 0;
        for (int i = 30; i >= 0; i = minus(i,1)) {
            if ((aValue >> i) >= bValue) {
                res |= 1 << i;
                aValue = minus(aValue, bValue << i);
            }
        }
        return isNeg(a) ^ isNeg(b) ? negNum(res) : res;
    }

    // 由于最大的负值无法算出绝对值, 故需要特殊处理
    // leetcode规定最大负值的绝对值就是最大正值
    // 最大负值先加一然后除一下的值记下来, 然后把原本的值减去这个值就可以继续除了, 最后把结果加起来即可
    public static int divide(int a, int b) {
        if (a == Integer.MIN_VALUE && b == Integer.MIN_VALUE) {
            return 1;
        } else if (b == Integer.MIN_VALUE) {
            return 0;
        } else if (a == Integer.MIN_VALUE) {
            if (b == -1) {
                return Integer.MAX_VALUE;
            } else {
                int res1 = div(add(a, 1), b);
                return add(res1,div(minus(a , multi(res1,b)),b));
            }
        } else {
            return div(a, b);
        }
    }
}
